# 81/100 动态规划-爬楼梯
# leetcode第70题: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/11/21
def climbStairs(n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


if __name__ == '__main__':
    print(climbStairs(2))
    print(climbStairs(3))
